package org.example;

import java.util.ArrayList;
import java.util.List;

public class Test1 {
    //leetcode 22 括号生成 https://leetcode.cn/problems/generate-parentheses/description/
    List<String> ret;
    StringBuilder path;
    int left,right;
    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        dfs(n);
        return ret;
    }

    private void dfs(int n) {
        if (left == n && right == n) {
            ret.add(path.toString());
            return;
        }

        if (left < n) {
            path.append("(");
            left++;
            dfs(n);
            path.deleteCharAt(path.length() - 1);
            left--;
        }

        if (left > right) {
            path.append(")");
            right++;
            dfs(n);
            path.deleteCharAt(path.length() - 1);
            right--;
        }
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        test1.generateParenthesis(3);
        System.out.println(888);
    }
}
